教材评价：

https://book.douban.com/subject/2308122/

下载地址：

http://m.wdfxw.net/Fulltext44364042.htm

这次回顾第4章：逻辑函数的优化。

专业术语

  • 因子：给定的乘积项包含多个变量，每个变量可能会以原变量或者反变量的形式出现。变量（不论原变量还是反变量）的每一次出现都称为一个因子（literal）。

    • 对于乘积项$\bar x_1 x_2$，一共有两个因子$\bar x_1, x_2$

  • 蕴涵项：若某个乘积项能说明输入变量的取值组合可以使给定函数（输出）为$1$，则称该乘积项为该函数的蕴涵项（implicant）。

    • 考虑如下函数：
    • 蕴涵项为：$\bar{x}_{1} \bar{x}_{2} \bar{x}_{3},\bar{x}_{1} \bar{x}_{2} x_{3}, \bar{x}_{1} x_{2} \bar{x}_{3}, \bar{x}_{1} x_{2} x_{3},x_1x_2x_3,\bar{x}_{1} \bar{x}_{2},\bar{x}_{1} \bar{x}_{3},\bar{x}_{1} x_{3},\bar{x}_{1} x_{2},x_{2} x_{3}$

  • 质蕴涵项：若某个蕴涵项不能再进一步合并为另外一个因子数更少的蕴涵项，则称该蕴涵项为质蕴涵项（prime implicant）。

    • 对于上述函数，质蕴涵项为$\bar x_1, x_2x_3$

  • 覆盖：若蕴涵项的集合能说明给定函数等于1的所有取值情况，则称该蕴涵项集合为该给定函数的覆盖（cover）。

    • 对于上述函数，覆盖有以及

  • 成本：统计逻辑电路中门的总数以及所有门的输入端的总数，把这两个数相加即得到电路成本。

  • 本质蕴涵项：若某个质蕴涵项含有其他质蕴涵项中没有的令$f = 1$的最小项，则该质蕴涵项必须被包含在覆盖之中，且被称为本质蕴涵项。

  • 无关条件（无关项）：不需考虑取值的输入。

  • 非完全指定函数：若函数含有无关条件，则称该函数为非完全指定函数。

卡诺图

卡诺图可以用来直接得到逻辑函数的最低成本电路。

二变量卡诺图

考虑逻辑函数

其卡诺图为

将相邻为$1$的单元合并可得

所以该函数的最低成本实现为

四变量卡诺图

注意同一行靠两侧为$1$的单元也是相邻。

备注：卡诺图相邻两个单元的二进制表示仅有一位不同。

最小化策略

求解给定函数最低成本实现的步骤如下：

  1. 生成给定函数的所有质蕴含项。
  2. 找出本质蕴涵项的集合。
  3. 如果本质蕴涵项的集合覆盖了所有$f=1$的取值情况，则这个集合就是函数$f$理想的最小成本覆盖。否则，确定应添加的非本质蕴涵项，以实现完整的最小成本覆盖。

例子：

通过卡诺图得到质蕴涵项：

只有$\bar x_3\bar x_4$是本质蕴涵项，接着随机选择质蕴涵项$x_{1} x_{2} x_{4}$，最后再加入$x_1\bar x_2 x_3$，所以一种实现方式为：

非完全指定函数

例子：

其中$D$表示无关项的集合。

卡诺图：

于是得到如下实现：

多级综合

思路：将函数

拆成多个子函数的复合函数，每个复合函数含有更少的输入变量。

例子：

提取公因子可得：

令

可得：

则函数$f$可以表示为：

立方体表示法

把$n$变量的逻辑函数映射为$n$维立方体称为立方体表示法，具体方法为将$f$表示为$f=1$的顶点集合。

三维立方体

再来看一个例子：

那么该逻辑函数可以表示为：

列表化简法(Quine-McCluskey)

以如下函数为例来讲解：

质蕴涵项的产生

根据最小项中$1$的个数进行分组得到下图：

由于立方体中没有变量，所以称为$0$维立方体。

然后对立方体合并得到$1$维立方体，得到下图：

重复此过程直至无法生成更高阶的立方体，最终得到下图：

将合并过的立方体做上标记，最后剩余的立方体即为质蕴涵项（因为无法再合并），即质蕴涵项的集合$P$为：

最小覆盖的确定

得到函数质蕴涵项的集合以后，我们需要从中找出一个覆盖所有使 $f = 1$的最小项的成本最低的子集。作为简化，我们假设电路成本和门的输人数目成正比，电路中门的输入个数与函数的质蕴涵项所含的因子数相等。

首先创建一个质蕴涵项覆盖表，表中每一行代表一个质蕴涵项，每一列表示一个最小项。如果某个最小项被质蕴含项覆盖，我们就在此质蕴涵项所在行与这个最小项所在列的交叉位置划上勾。

如果覆盖表中某一列只有一个勾，那么就说明只有一个质蕴涵项覆盖这个最小项，所以该质蕴含项必须包含在最终的覆盖中，我们称其为本质蕴涵项，例如上图中的$p_6$。

删除本质蕴涵项得到下图：

接着介绍行支配的概念。

行支配：如果$p_i =1\Rightarrow p_j=1$，那么称$p_j$支配$p_i$。

对于上图，显然有$p_2$支配$p_1$。

化简步骤的下一步是在覆盖表中删除被支配的质蕴涵项，删除后得到下图：

从上图中可以看出必须要选择$p_2,p_5$，所以最终的覆盖为

最低成本实现是

最后补充列支配的概念：假设最小项$m_i,m_j$对应的覆盖分别为$P_i, P_j$，如果$P_i\subseteq P_j$，那么称$m_j$列支配$m_i$。

此时化简的过程是删除支配列，因为当我们选择一个质蕴涵项去覆盖被支配列所对应的最小项时，这个质蕴涵项也将覆盖支配列对应的最小项。

来看一个列支配的例子：

质蕴涵项产生的过程：

所以最后的质蕴涵项为

化简过程：

最终化简结果：

总结
  1. 首先，列一个表格，使令逻辑函数$f$为$1$的最小项以及无关项都包含在其中，用立方体的连续配对比较方法，产生函数的质蕴涵项。
  2. 列一个初始的质蕴涵项覆盖表，使$f$为$1$的所有最小项都包含在其中。
  3. 使本质蕴涵项包含在最终覆盖表中（如果有的话），通过移去质蕴涵项和被覆盖的最小项的方法化简覆盖表。
  4. 用行支配和列支配的概念进一步化简覆盖表。只有在被支配行的质蕴含项的成本大于或等于支配行的质蕴含项的成本时，才把被支配行移去。
  5. 重复步何3和4直到覆盖表变空或者不可能进一步化简。
  6. 如果化简后的覆盖表不为空，则用分支方法确定余下的质蕴涵项中哪些应该包含在最低成本的覆盖中。

使用立方体表示法最小化函数

两种运算
星积运算

假设$A,B$为$n$变量函数中的两个蕴涵项：

定义

该运算满足如下两个规则：

  1. 当在多于一个坐标上$A_{i} \star B_{i}=\varnothing$ 时， $C=\varnothing$
  2. 当以上条件不满足时，若$A_i \star B_{i} \neq \varnothing$，则$C_{i}=A_{i} \star B_{i},$ 若 $A_{i} * B_{i}=\varnothing,$ 则 $C_{i}=x$
$\sharp$运算

假设$A,B$为$n$变量函数中的两个蕴涵项：

定义

该运算满足如下三个规则：

  1. 如果存在某个$i$使$A_{i} \sharp B_{i}=\varnothing$， 则$C=A$

  2. 如果对所有的$i$都使$A_{i} \sharp B_{i}=\varepsilon$，则$C=\varnothing$

  3. 如果以上两条规则的条件都不满足，则对于满足条件$A_{i}=x, B_{i} \neq x$的$i$：

求解质蕴涵项

可以利用星积运算求解本质蕴涵项，具体步骤如下，假设$f$的立方体表示为$C^k$，对$C^k$中任意两个元素$c^i,c^j$做星积运算，得到$G^{k+1}$，即

令

重复上述过程直至$C^{i+1}=C^i$，那么$C^i$即为质蕴涵项。

本质蕴涵项的确定

假设函数$f$的质蕴涵项的集合为$P$，$DC$为其无关项所代表的顶点集合，那么当且仅当

$p^i$为函数$f$的本质蕴涵项。

求解最小覆盖的完整步骤

称$f=1$的顶点集合为开集，记为$ON$，那么求解最小覆盖的的过程如下：

  1. 令$C^{0}=O N \cup D C$为逻辑函数$f$及其无关项的初始覆盖。
  2. 用星积运算找出$C$的所有质蕴涵项，令$P$为所得的质蕴涵项集合。
  3. 用$\sharp$运算找出所有本质蕴涵项。若本质蕴涵项包含了开集（$ON$）中所有的顶点，则该本质蕴涵项集合组成最小化覆盖。
  4. 若质蕴涵项$p^i$比质蕴涵项$p^j$成本要高，而且 $p^{i} \sharp D C \sharp p^{j}=\varnothing$ ，則将$p^{i}$刪去。
  5. 找出覆盖所有剩余顶点的成本最低的质蕴涵项。如果各个质蕴涵项的成本相同，则对剩余的质蕴涵项使用启发式的分支法求得成本最低的覆盖。